#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define F(b, c, d) ((b & c) | (~b & d))        // 第一轮
#define G(b, c, d) ((b & d) | (c & ~d))        // 第二轮
#define H(b, c, d) (b ^ c ^ d)                 // 第三轮
#define I(b, c, d) (c ^ (b | ~d))              // 第四轮
#define CLS(x, s) ((x << s) | (x >> (32 - s))) // 循环左移

unsigned char *processedText; //填充完毕的字符串
unsigned int *processedInt;   //由填充完的字符串转成的数组
unsigned char hashRes[17];
long blocklength;             //MD5算法最终512位的块数

//初始的向量
const unsigned int IV[4] = {
    0x67452301,
    0xEFCDAB89,
    0x98BADCFE,
    0x10325476};

//每次迭代更新的向量
unsigned int CV[4] = {
    0x67452301,
    0xEFCDAB89,
    0x98BADCFE,
    0x10325476};

//压缩函数中的T表
const int T_table[] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
    0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
    0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
    0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
    0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
    0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

//每轮循环的一次迭代中的移位运算位数
const int S_table[] = {
    7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
    5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
    4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
    6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};

//MD5数据结构
typedef struct
{
    unsigned int eachByte[4];
} MD5_RES;

//初始化最开始的CV
void CVinit()
{
    CV[0] = 0x67452301;
    CV[1] = 0xEFCDAB89;
    CV[2] = 0x98BADCFE;
    CV[3] = 0x10325476;
}

//将字符串转换成数组
void TexttoInt(unsigned char *src, unsigned int *dst, unsigned long textLength)
{
    
    for (int i = 0; i < textLength / 4; i++)
    {
        dst[i] = (src[i * 4]) |
                 (src[i * 4 + 1] << 8) |
                 (src[i * 4 + 2] << 16) |
                 (src[i * 4 + 3] << 24);
    }
}

//将数组变成字符串
void InttoText(unsigned int *src, unsigned char *dst, unsigned long intLength)
{
    for (int i = 0; i < intLength; i++)
    {
        dst[i * 4 + 3] = (src[i] >> 24) & 0x000000ff;
        dst[i * 4 + 2] = (src[i] >> 16) & 0x000000ff;
        dst[i * 4 + 1] = (src[i] >> 8) & 0x000000ff;
        dst[i * 4] = src[i] & 0x000000ff;
    }
}

//根据MD5的要求填充原始的原文
void padText(unsigned char *originalText, unsigned long textLength){
    int i;
    blocklength = textLength / 64 + ((textLength * 8) % 512 > 448 ? 2 : 1);
    processedText = (unsigned char *)malloc(sizeof(char)*blocklength * 64);
    for (i = 0; i < textLength; i++)
    {
        processedText[i] = originalText[i];
    }
    //字符串的填充
    processedText[textLength] = 0x80;

    for (i = textLength + 1; i < blocklength * 64; i++)
    {
        processedText[i] = 0;
    }

    processedInt = (unsigned int *)malloc(sizeof(int) * blocklength * 16);//每个int的长度为32，所以一共的字数等于块数16
    TexttoInt(processedText, processedInt, blocklength * 64);

    //计算最后补充的64位
    // unsigned int high = ((textLength * 8) >> 32) & 0x00000000ffffffff;
    unsigned int low = (textLength * 8) & 0x00000000ffffffff;
    unsigned int high = 0;
    processedInt[blocklength * 16 - 2] = low;
    processedInt[blocklength * 16 - 1] = high;
}

//每一轮的压缩函数
void H_MD5_subLoop(unsigned int *Y)
{
    int i, j;
    unsigned int currentCV[4];
    unsigned int nextCV[4];
    for (i = 0; i < 4; i++)
    {
        currentCV[i] = CV[i];
        nextCV[i] = CV[i];
    }
    //一共4轮循环，每一轮16步
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 16; j++)
        {
            if (i == 0)
            {
                nextCV[1] = currentCV[1] + CLS(currentCV[0] + F(currentCV[1], currentCV[2], currentCV[3]) + Y[j] + T_table[i * 16 + j], S_table[i * 16 + j]);
            }
            else if (i == 1)
            {
                nextCV[1] = currentCV[1] + CLS(currentCV[0] + G(currentCV[1], currentCV[2], currentCV[3]) + Y[(1 + 5 * j) % 16] + T_table[i * 16 + j], S_table[i * 16 + j]);
            }
            else if (i == 2)
            {
                nextCV[1] = currentCV[1] + CLS(currentCV[0] + H(currentCV[1], currentCV[2], currentCV[3]) + Y[(5 + 3 * j) % 16] + T_table[i * 16 + j], S_table[i * 16 + j]);
            }
            else if (i == 3)
            {
                nextCV[1] = currentCV[1] + CLS(currentCV[0] + I(currentCV[1], currentCV[2], currentCV[3]) + Y[(7 * j) % 16] + T_table[i * 16 + j], S_table[i * 16 + j]);
            }
            nextCV[2] = currentCV[1];
            nextCV[3] = currentCV[2];
            nextCV[0] = currentCV[3];

            currentCV[0] = nextCV[0];
            currentCV[1] = nextCV[1];
            currentCV[2] = nextCV[2];
            currentCV[3] = nextCV[3];
        }
    }
    for (i = 0; i < 4; i++)
    {
        CV[i] += nextCV[i];
    }
}

//真正的压缩函数
MD5_RES H_MD5(){
    CVinit();
    MD5_RES res;
    int i,j;
    unsigned int tempY[16];
    for(i = 0;i<blocklength;i++){
        for(j = 0;j<16;j++){
            tempY[j] = processedInt[16*i+j];
        }
        H_MD5_subLoop(tempY);
    }
    for (i = 0; i < 4; i++)
    {
        res.eachByte[i] = CV[i];
    }
    return res;
}

//释放所有的动态内存
void freeAll(){
    free(processedInt);
    free(processedText);
}

//最终的MD5函数
void MD5(unsigned char *message,unsigned long messageLength){
    padText(message, messageLength);
    MD5_RES res = H_MD5();
    InttoText(res.eachByte, hashRes, 4);
    hashRes[16] = 0;
    freeAll();
}